package com.love.labuladong.twopoint.slidewindow;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author : zh
 * @Description : 438. 找到字符串中所有字母异位词
 * @Date : 2024-09-02 17:17
 */
public class DiffPointChar {

    /**
     * 此种解法，valid ：在window中多出来所需要的字符也是不算的。
     * 而且是采用的固定窗口
     * @param s
     * @param p
     * @return
     */
    public static List<Integer> findAnagrams(String s, String p) {
        int n = s.length();
        int l = 0,r = 0;
        int[] w = new int[26];
        // 这是固定字串的频率[其实这个就是做一个缓存作用，用于快速查找吧你]
        int[] table = new int[26];
        List<Integer> res = new LinkedList<>();
        // 先把字串字符的频率打表
        for (int i = 0; i < p.length(); i++) {
            char c = p.charAt(i);
            table[c - 'a']++;
        }
        // 记录有效字母的个数
        int valid = 0;
        while (r < n){
            char c = s.charAt(r);
            // window 里面，有效的，无效的都装
            w[c - 'a']++;
            r++;
            // 表示字串中有这字母
            if(table[c - 'a'] > 0){
                // 给滑动窗口中加入此字母频次
                if(w[c - 'a'] <= table[c - 'a']){
                    valid++;
                }
            }
            // 固定窗口(l 指针移动)
            while (r - l >= p.length()){
                char lc = s.charAt(l);
                if(valid == p.length()){
                    res.add(l);
                }
                l++;
                if(table[lc - 'a'] > 0){
                    if(w[lc - 'a'] <= table[lc - 'a']){
                        valid--;
                    }
                }
                w[lc - 'a']--;
            }
        }
        return res;
    }


    /**
     * 解法其实和上述一样
     * @param s
     * @param p
     * @return
     */
    public static List<Integer> findAnagrams1(String s, String p) {
        char[] sc = s.toCharArray();
        char[] pc = p.toCharArray();
        int[] need = new int[128];
        int[] w = new int[128];
        for(char c : pc){
            need[c]++;
        }
        List<Integer> ans = new LinkedList<>();
        int l = 0, r = 0;
        int valid = 0;
        int n = sc.length;
        int m = pc.length;
        while(r < n){
            char ch = sc[r];
            if(need[ch] > 0 ){
                if(w[ch] < need[ch]){
                    valid++;
                }
            }
            w[ch]++;
            while(r - l + 1 == m ){
                if(valid == m){
                    ans.add(l);
                }
                char c = sc[l];
                if(need[c] > 0){
                    if(w[c] <= need[c]){
                        valid--;
                    }
                }
                w[c]--;
                l++;
            }
            r++;
        }
        return ans;

    }


    public static void main(String[] args) {
//        String s = "gcbaebabacd";
        String s = "cbaebabacd";

        String p = "abc";


        List<Integer> list = findAnagrams1(s, p);

        System.out.println(Arrays.toString(list.toArray()));

    }

}
